package leetcode.binaryTree;

import datastructure.tree.TreeNode;

/**
 * @Description: https://leetcode.cn/problems/largest-bst-subtree/
 * @Author Ammar
 * @Create 2023/7/17 22:48
 */
public class _333_最大BST子树 {
    public int largestBSTSubtree(TreeNode root) {
        return (root == null) ? 0 : getInfo(root).size;
    }

    /**
     * 返回 最大 BST 的信息
     * @param root
     * @return
     */
    public TreeInfo getInfo(TreeNode<Integer> root) {
        if (root == null) return null;
        TreeInfo leftInfo = getInfo(root.left);
        TreeInfo rightInfo = getInfo(root.right);

        if (leftInfo != null && rightInfo != null) {
            if (leftInfo.root == root.left && leftInfo.max < root.val
                    && rightInfo.root == root.right && rightInfo.min > root.val)
                return new TreeInfo(root, leftInfo.size + rightInfo.size + 1, rightInfo.max, leftInfo.min);
            else {
                if (leftInfo.size < rightInfo.size) return rightInfo;
                else return leftInfo;
            }
        } else if (rightInfo == null && leftInfo != null) {
            if (leftInfo.root == root.left && leftInfo.max < root.val) return new TreeInfo(root, leftInfo.size + 1, root.val, leftInfo.min);
            else return leftInfo;
        } else if (leftInfo == null && rightInfo != null) {
            if (rightInfo.root == root.right && rightInfo.min > root.val) return new TreeInfo(root, rightInfo.size + 1, rightInfo.max, root.val);
            else return rightInfo;
        } else {
            return new TreeInfo(root, 1, root.val, root.val);
        }
    }


    private static class TreeInfo {
        TreeNode root;
        int size;
        int max;
        int min;

        public TreeInfo(TreeNode root, int size, int max, int min) {
            this.root = root;
            this.size = size;
            this.max = max;
            this.min = min;
        }
    }
}
